package codeTop;

public class q79 {
    public boolean exist(char[][] board, String word) {
        boolean[][] visit = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    dfs(board,word,0,i,j,visit);
                    if (flag) {
                        return true;
                    }
                }
            }
        }
        return flag;
    }

    boolean flag = false;
    private void dfs(char[][] board, String word, int idx, int i, int j,boolean[][] visit) {
        visit[i][j] = true;
        if (flag) {
            return;
        }
        if (idx == word.length() - 1) {
            flag = true;
            return;
        }
        //上
        if (i > 0&&board[i-1][j]==word.charAt(idx+1)&&!visit[i-1][j]) {
            dfs(board,word,idx+1,i-1,j,visit);
        }
        //下
        if (i < board.length - 1 && board[i + 1][j] == word.charAt(idx + 1)&&!visit[i + 1][j]) {
            dfs(board,word,idx+1,i+1,j,visit);
        }
        //左
        if (j > 0 && board[i][j - 1] == word.charAt(idx + 1)&&!visit[i][j - 1]) {
            dfs(board,word,idx+1,i,j-1,visit);
        }
        //右
        if (j < board[0].length - 1 && board[i][j + 1] == word.charAt(idx + 1)&&!visit[i][j + 1]) {
            dfs(board,word,idx+1,i,j+1,visit);
        }
        visit[i][j] = false;
    }
}
